package com.spd.sort;

import java.util.Arrays;

/**
 * 堆排序。过程包括  
 * 1. 初始化需要排序的数组对象。
 * 2. 递归建立最大堆或者最小堆。
 * @author xianchao
 *
 */
public class HeapSort {

	//测试一个数组
	private int[] array = null;//new int[]{78, 12, 34, 98, 34, 56, 73, 19, 9, 10, 28, 11};
	
	private int rootCnt = 0, leafStartIndex = 0;
	
	/**
	 * 初始化根节点数，叶子节点
	 * 根：array.length / 2。总数 / 2 取整。
	 * 节点：array.length - array.length / 2。总数 - 根的数
	 */
	public void init(int[] array) {
		this.array = array;
		rootCnt = array.length / 2;
		leafStartIndex = rootCnt;
	}
	
	/**
	 * 从节点开始，逐次和左右子节点做对比，找最大的子节点，进行交换
	 * 子节点继续和它的子节点做对比，直到叶子节点为止
	 */
	public void buildItemMaxHeap(int index) {
		while(index < leafStartIndex) {
			//从根，左右子节点中找到最大的值对应的下标
			int leftIndex = index * 2 + 1;
			int rightIndex = index * 2 + 2;
			int maxIndex = index;
			if(array[leftIndex] > array[index]) {
				maxIndex = leftIndex;
			}
			if(rightIndex < array.length && array[rightIndex] > array[maxIndex]) {
				maxIndex = rightIndex;
			}
			if(maxIndex != index) {
				//交换
				int temp = array[maxIndex];
				array[maxIndex] = array[index];
				array[index] = temp;
				//交换完了之后，再递归交换后的节点
				index = maxIndex;
			} else {
				break;
			}
		}
	}
	
	public void buildMaxHeap() {
		int maxRoot = array.length / 2 - 1;
		for(int i = maxRoot; i >= 0; i--) {
			buildItemMaxHeap(i);
		}
	}
}
